package Ali;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * 小扣在秋日市集选择了一家早餐摊位，一维整型数组 staple 中记录了每种主食的价格，
 * 一维整型数组 drinks 中记录了每种饮料的价格。小扣的计划选择一份主食和一款饮料，
 * 且花费不超过 x 元。请返回小扣共有多少种购买方案。
 * @author le
 */
public class Test06
{
    public static void main(String[] args)
    {

    }

    public int breakfastNumber(int[] staple, int[] drinks, int x) {
        Arrays.sort(staple);
        Arrays.sort(drinks);
        int cnt=0;
        int m=staple.length,n=drinks.length;
        int i=0,j=n-1;
        while(i<m&&j>=0){
            if(staple[i]+drinks[j]<=x){
                cnt=(cnt+j+1)%1000000007;
                i++;
            }else{
                j--;
            }
        }
        return cnt%1000000007;
    }

    public static void quickSort(int[] arr,int left,int right){
        if (left < right){
            int key = arr[left];

            int i = left;
            int j = right;

            while(i < j){
                while(i < j && arr[j] > key){
                    j--;
                }
                while(i < j){
                    arr[i++] = arr[j];
                }
                while(i < j && arr[i] < key){
                    i++;
                }
                while(i < j){
                    i++;
                }
            }
            arr[i] = key;
            quickSort(arr,0,i-1);
            quickSort(arr,i+1,right);



        }
    }
}
